package Exercise;

import java.util.ArrayList;

public class KMin {

    public static ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        if (input == null || input.length < k)
            return null;
        ArrayList<Integer> list = new ArrayList<>();
        GetLeastNumbers_Solution(input, 0, input.length - 1, k);
        for (int i = 0; i < k; ++i)
            list.add(input[i]);
        return list;
    }

    private static void GetLeastNumbers_Solution(int[] input, int low, int high, int k) {
        int mid = (low + high) >> 1;
        int start = low;
        int end = high;
        int temp = input[start];
        while (start < end) {
            while (start < end && input[end] > temp)
                end--;
            if (start < end)
                input[start++] = input[end];
            while (start < end && input[start] <= temp) {
                start++;
            }
            if (start < end)
                input[end--] = input[start];
        }
        input[start] = temp;

        if (start == k-1)
            return;
        else if (start > k-1)
            GetLeastNumbers_Solution(input, low, start - 1, k);
        else
            GetLeastNumbers_Solution(input, start + 1, high, k);
    }

    public static void main(String[] args) {
        int[] array = {4,5,1,6,2,7,2,8};
        ArrayList<Integer> integers = GetLeastNumbers_Solution(array, 2);
        for (Integer i : integers) {
            System.out.println(i);
        }
    }
}
